//
// Created by LiuYou on 2021/12/4.
//

#include <iostream>
#include <vector>
#include <random>
#include <iterator>
#include <algorithm>


/**
 * @brief 从区间 [left, right] 上等概率返回一个值。
 * @param left 左边界
 * @param right 右边界
 * @return 返回区间 [left, right] 上的一个随机数。
 */
static int randomNum(int left, int right) {
    std::random_device randomDevice;
    std::default_random_engine randomEngine( randomDevice());
    std::uniform_int_distribution<> uniformIntDistribution( left, right );
    return uniformIntDistribution( randomEngine );
}


static void selectionSort(std::vector<int>& arr) {
    if (arr.empty() || arr.size() == 1) {
        return;
    }

    for (int i = 0; i < arr.size() - 1; ++i) {
        int minIndex = i;
        for (int j = i + 1; j < arr.size(); ++j) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        std::swap( arr[i], arr[minIndex] );
    }
}


int main(int argc, char** argv) {
    {
        std::vector<int> arr;
        arr.reserve( 10 );

        std::cout << "arr.size() = " << arr.size() << std::endl;
        std::cout << "arr.capacity() = " << arr.capacity() << std::endl;


        std::vector<int> arr1( 10 );

        std::cout << "arr1.size() = " << arr1.size() << std::endl;
        std::cout << "arr1.capacity() = " << arr1.capacity() << std::endl;


        std::vector<int> arr2;

        std::cout << "arr2.size() = " << arr2.size() << std::endl;
        std::cout << "arr2.capacity() = " << arr2.capacity() << std::endl;
        // 运行结果:
        /*
            arr.size() = 0
            arr.capacity() = 10
            arr1.size() = 10
            arr1.capacity() = 10
            arr2.size() = 0
            arr2.capacity() = 0
         */
    }

    std::cout << "===============================[ selection sort ]=================================" << std::endl;

    {
        std::vector<int> arr;
        arr.reserve( 10 );

        for (int i = 0; i < 10; ++i) {
            arr.push_back( randomNum( 0, 100 ));
        }

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << std::endl;

        selectionSort( arr );

        std::copy( arr.begin(), arr.end(), std::ostream_iterator<int>( std::cout, "\t" ));
        std::cout << std::endl;

        std::cout << "有序: " << std::boolalpha << std::is_sorted( arr.begin(), arr.end()) << std::endl;

    }


    return 0;
}
